/* 

给定一个字符串 s 和一个非空字符串 p，找到 s 中所有是 p 的字母异位词的子串，返回这些子串的起始索引。

字符串只包含小写英文字母，并且字符串 s 和 p 的长度都不超过 20100。

说明：

字母异位词指字母相同，但排列不同的字符串。
不考虑答案输出的顺序。
示例 1:

输入:
s: "cbaebabacd" p: "abc"

输出:
[0, 6]

解释:
起始索引等于 0 的子串是 "cba", 它是 "abc" 的字母异位词。
起始索引等于 6 的子串是 "bac", 它是 "abc" 的字母异位词。
 示例 2:

输入:
s: "abab" p: "ab"

输出:
[0, 1, 2]

解释:
起始索引等于 0 的子串是 "ab", 它是 "ab" 的字母异位词。
起始索引等于 1 的子串是 "ba", 它是 "ab" 的字母异位词。
起始索引等于 2 的子串是 "ab", 它是 "ab" 的字母异位词。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/find-all-anagrams-in-a-string
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

*/

/**
 * @param {string} s
 * @param {string} p
 * @return {number[]}
 */
// 滑动窗口
var findAnagrams = function (s, p) {
    let res = [];
    let need = new Map();
    for (let i = 0; i < p.length; i++) {
        need.set(p[i], need.has(p[i]) ? need.get(p[i]) + 1 : 1);
    }

    let left = 0,
        right = 0;
    let vaild = 0;
    let window = new Map();

    while (right < s.length) {
        let char = s[right];

        if (need.has(char)) {
            window.set(char, window.has(char) ? window.get(char) + 1 : 1);
            if (window.get(char) === need.get(char)) {
                vaild++;
            }
        }

        while (right - left + 1 >= p.length) {
            if (vaild === need.size) {
                res.push(left);
            }
            let leave = s[left];
            if (need.has(leave)) {
                if (window.get(leave) === need.get(leave)) {
                    vaild--;
                }
                window.set(leave, window.get(leave) - 1);
            }
            left++;
        }

        right++;
    }

    return res;
};

// 滑动窗口（注释版）
var findAnagrams = function (s, p) {
    // 用于保存结果
    let res = []
    // 用于统计p串所需字符
    let need = new Map()
    for (let i = 0; i < p.length; i++) {
        need.set(p[i], need.has(p[i]) ? need.get(p[i]) + 1 : 1)
    }
    // 定义滑动窗口
    let left = 0,
        right = 0,
        valid = 0
    // 用于统计窗口中的字符
    let window = new Map()
    // 遍历s串
    while (right < s.length) {
        // 进入窗口的字符
        let c = s[right]
        // 扩大窗口
        right++
        // 进入窗口的字符是所需字符
        if (need.has(c)) {
            // 更新滑动窗口中的字符记录
            window.set(c, window.has(c) ? window.get(c) + 1 : 1)
            // 当窗口中的字符数和滑动窗口中的字符数一致
            if (window.get(c) === need.get(c)) {
                // 有效字符自增
                valid++
            }
        }
        // 当滑动窗口的大小超出p串长度时 收缩窗口
        while (right - left >= p.length) {
            // 有效字符和所需字符数一致 找到一条符合条件的子串
            if (valid === need.size) {
                // 保存子串的起始索引位置
                res.push(left)
            }
            // 离开窗口的字符
            let d = s[left]
            // 收缩窗口
            left++
            // 如果离开窗口字符是所需字符
            if (need.has(d)) {
                // 如果离开字符数和所需字符数一致
                if (window.get(d) === need.get(d)) {
                    // 有效字符减少一个
                    valid--
                }
                // 更新滑动窗口中的字符数
                window.set(d, window.get(d) - 1)
            }
        }
    }
    // 返回结果
    return res
};